<?php
/*
 * 某游戏是一个卡牌类游戏，玩家通过战斗或抽牌可以拿到一些技能牌，每张技能牌都有对应的伤害值(伤 害值>=0)，
 * 当你有了组合技属性之后，你可以在自己手头上选择任意张技能牌，以组合技的方式来攻击 boss，
 * 组合技的总伤害将等于所组合的各张技能牌的伤害值的乘积(只有一张牌时，组合技伤害值等于这张牌 本身的伤害值)，
 * 但是能发动组合技必须有个前提:所有被选择的技能牌的伤害系数之和必须等于m(m>0) 以解开封印;
 * 你为了能赢得最终胜利，需要在所有技能牌中挑出若干张技能牌触发组合技(每张牌只能用一 次)，以形成最大威力的组合技攻击效果。
 * 例如:
 * 你有伤害值分别为1,2,3,4,5的五张牌，给定的解开封印的阈值(m)为10，
 * 那形成最大组合攻击效果 的组合为30(5*3*2)，而不是24(4*3*2*1)，也不是20(5*4*1)，
 * 需要输出的结果即30。
 */

// 题意就是：sum定死的前提下求最大的乘积
$arr = [1, 2, 3, 4, 5];
$sum = 10;
$obj = new Code_01_CardGame();
$obj->main($arr, $sum);
$obj->main2($arr, $sum);

class Code_01_CardGame
{
    // 递归
    public function main($arr, $sum)
    {
        $res = $this->_process($arr, 0, $sum);
        echo $res . PHP_EOL;
    }

    protected function _process($arr, $index, $sum)
    {
        if ($sum < 0) {
            return -1;
        }
        if ($index == count($arr)) {
            return $sum == 0 ? 1 : -1;
        }
        // 不要当前的数
        $notInclude = $this->_process($arr, $index + 1, $sum);
        // 要当前的数
        $include    = $arr[$index] * $this->_process($arr, $index + 1, $sum - $arr[$index]);

        return max($notInclude, $include);
    }

    // DP
    public function main2($arr, $sum)
    {
        $len = count($arr);
        if ($arr == null || $len == 0) {
            return 0;
        }
        $dp = array_fill(0, $len, array_fill(0, $sum+1, 0));
		if ($arr[0] <= $sum) {
            $dp[0][$arr[0]] = $arr[0];
        }
		for ($i = 1; $i < $len; $i++) {
            for ($j = 0; $j <= $sum; $j++) {
                $no = $dp[$i - 1][$j];
				$only = $j - $arr[$i] == 0 ? $arr[$i] : 0;
				$part = $j - $arr[$i] > 0 ? $dp[$i - 1][$j - $arr[$i]] * $arr[$i] : 0;
				$dp[$i][$j] = max($no, $only, $part);
			}
		}
//		print_r($dp);die;
        echo $dp[count($dp) - 1][count($dp[0]) - 1]. PHP_EOL;
    }
}